#include<iostream>
#include<vector>
#include<string>
#include<set>
#include<map>
#include<stack>
#include<algorithm>
using namespace std;


class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        for(int i = 0;i<edges.size();++i){
            int left = edges[i][0];
            int right = edges[i][1];
            if(parent.find(left)==parent.end())
                parent[left] = left;
            if(parent.find(right)==parent.end())
                parent[right] = right;
            if(!isSameSet(left,right)){
                unionSet(left,right);
            }
            else{
                return {left,right};
            }

        }
        return {};
            
        }
     int findFather(int a){
            stack<int> path;
            while(parent[a]!=a){
                path.push(a);
                a = parent[a];
            }
            while(!path.empty()){
                parent[path.top()] = a;
                path.pop();
            }
            return a;
        }
    bool isSameSet(int a,int b){
        return findFather(a)==findFather(b);
    }
    void unionSet(int a,int b){
        if(!isSameSet(a,b)){
            int afather = findFather(a);
            int bfather = findFather(b);
            parent[afather] = bfather;
        }
    }
public:
    map<int,int> parent;

};

int main(){
    Solution S;
    vector<vector<int>> V = {{3,4},{1,2},{2,4},{3,5},{2,5}};
    vector<int> result = S.findRedundantConnection(V);
    return 0;
}